The rapid growth of electronic mail systems, electronic funds transfer systems and the like has increased concerns over the security of the data transferred over unsecured communication channels. Cryptographic systems are widely used to insure the privacy and authenticity of messages communicated over such insecure channels.
In a conventional cryptographic system, a method of encryption is utilized to transform a plain text message into a message which is unintelligible. Thereafter, a method of decryption is utilized for decoding the encrypted message to restore the message to its original form.
Conventional crypotographic signature and authentication systems typically utilize a "one way" hashing function to transform the plain text message into a form which is unintelligible. A "hashing" function as used herein is a function which can be applied to an aggregation of data to create a smaller, more easily processed aggregation of data.
An important characteristic of the hashing function is that it be a "one-way" function. A hash is a "one-way" function, if it is far more difficult to compute the inverse of the hashing function than it is to compute the function. For all practical purposes, the value obtained from applying the hashing function to the original aggregation of data is an unforgeable unique fingerprint of the original data. If the original data is changed in any manner, the hash of such modified data will likewise be different.
In conventional cryptographic systems, binary coded information is encrypted into an unintelligible form called cipher and decrypted back into its original form utilizing an algorithm which sequences through encipher and decipher operations utilizing a binary code called a key. For example, the National Bureau of Standards in 1977 approved a block cipher algorithm referred as the Data Encryption Standard (DES). Data Encryption Standard, FIPS PUB 46, National Bureau of Standards, Jan. 5, 1977.
In DES, binary coded data is cryptographically protected using the DES algorithm in conjunction with a key. Each member of a group of authorized users of encrypted computer data must have the key that was used to encipher the data in order to use it. This key held by each member in common is used to decipher the data received in cipher form from other members of the group.
The key chosen for use in a particular application makes the results of encrypting data using the DES algorithm unique. Selection of a different key causes the cipher that is produced for a given set of inputs to be different. Unauthorized recipients of the cipher text who know the DES algorithm, but who do not have the secret key, cannot derive the original data algorithmically.
Thus, the cryptographic security of the data depends on the security provided for the key used to encipher and decipher the data. As in most conventional cryptographic systems the ultimate security of the DES system critically depends on maintaining the secrecy of the cryptographic key. Keys defined by the DES system include sixty-four binary digits of which fifty-six are used directly by the DES algorithm as the significant digits of the key and eight bits are used for error detection.
In such conventional cryptographic systems, some secure method must be utilized to distribute a secret key to the message sender and receiver. Thus, one of the major difficulties with existing cryptographic systems is the need for the sender and receiver to exchange a single key in such a manner that an unauthorized party does not have access to the key.
The exchange of such a key is frequently done by sending the key, prior to a message exchange, via, for example, a private courier or registered mail. While providing the necessary security such key distribution techniques are usually slow and expensive. If the need for the sender and receiver is only to have one private message exchange, such an exchange could be accomplished by private courier or registered mail, thereby rendering the cryptographic communication unnecessary. Moreover, if the need to communicate privately is urgent the time required to distribute the private key causes an unacceptable delay.
Public key cryptographic systems solve many of the key distribution problems associated with conventional cryptographic systems. In public key cryptographic systems the encrypting and decrypting processes are decoupled in such a manner that the encrypting process key is separate and distinct from the decrypting process key. Thus, for each encryption key there is a corresponding decryption key which is not the same as the encryption key. Even with knowledge of the encryption key, it is not feasible to compute the decryption key.
With a public key system, it is possible to communicate privately without transmitting any secret keys. The public key system does require that an encryption/decryption key pair be generated. The encryption keys for all users may be distributed or published and anyone desiring to communicate simply encrypts his or her message under the destination user's public key.
Only the destination user, who retains the secret decrypting key, is able to decipher the transmitted message. Revealing the encryption key discloses nothing useful about the decrypting key, i.e., only persons having knowledge of the decrypting can decrypt the message. The RSA cryptographic system which is disclosed in U.S. Pat. No. 4,405,829 issued to Rivest et al. discloses an exemplary methodology for a practical implementation of a public key cryptographic system.
A major problem in public key and other cryptographic systems is the need to confirm that the sender of a received message is actually the person named in the message. An authenticating technique known utilizing "digital signatures" allows a user to employ his secret key to "sign a message" which the receiving party or a third party can validate using the originator's public key. See for example U.S. Pat. No. 4,405,829.
A user who has filed a public key in a publicly accessible file can digitally sign a message by decrypting the message or a hash of it with the user's private key before transmitting the message. Recipients of the message can verify the message or signature by encrypting it with the sender's public encryption key. Thus, the digital signature process is essentially the reverse of the typical cryptographic process in that the message is first decrypted and then encrypted. Anyone who has the user's public encryption key can read the message or signature, but only the sender having the secret decryption could have created the message or signature.
Serious problems still persist in public key cryptosystems of assuring that a specified public key is that actually created by the specified individual. One known technique for addressing this problem is to rely on some trusted authority, e.g., a governmental agency, to insure that each public key is associated with the person who claiming to be the true author.
The trusted authority creates a digital message which contains the claimant's public key and the name of the claimant (which is accurate to the authority's satisfaction) and a representative of the authority signs the digital message with the authority's own digital signature. This digital message, often known as a certificate, is sent along with the user of the claimant's own digital signature. Any recipient of the claimant's message can trust the signature, provided that the recipient recognizes the authority's public key (which enables verification of the authority's signature) and to the extent that the recipient trusts the authority.
Prior to the present invention, the transmitted certificate failed to provide any indication of the degree of trust or the level of responsibility with which the sender of the message should be empowered. Instead, the certification merely indicates that the identified trusted authority recognized the sender's public key as belonging to that person.
The public key system is designed to operate such that the public keys of various users are published to make private communications easier to accomplish. However, as the number of parties who desire to use the public key system expands, the number of published keys will soon grow to a size where the issuing authority of the public keys can not reasonably insure that the parties whose public keys are published are, in fact, the people who they are claiming to be. Thus, a party may provide a public key to be maintained in the public directory under the name of the chairman of a major corporation, e.g., for example, General Motors Corporation. Such an individual may then be in a position to receive private messages directed to the chairman of General Motors or to create signatures which ostensibly belong to the impersonated chairman.
There are also technologies for producing digital signatures which may not require full public key capability, including, for example, the Fiat-Shamir algorithm. Any digital signature methodology may be employed to implement the digital signatures referenced herein. Any reference to public key cryptosystems should also be construed to reflect signature systems. Any reference to public key decryption should be taken as a generalized reference to signature creation and any reference to encryption should be taken as a reference to signature verification.
The present invention addresses such problems with the public key or signature cryptographic system relating to authenticating the identity of the public key holder by expanding the capability of digital signature certification. In this regard, a certification methodology is utilized which employs multiple level certification while at the same time indicating the authority and responsibility levels of the individual whose signature is being certified as is explained in detail below.
The present invention enhances the capabilities of public key cryptography so that it may be employed in a wider variety of business transactions, even those where two parties may be virtually unknown to each other.
The digital signature certification method and apparatus of the present invention provides for a hierarchy of certifications and signatures. It also allows for co-signature requirements. In this regard, counter-signature and joint-signature requirements are referenced in each digital certification to permit business transactions to take place electronically, which heretofore often only would take place after at least one party physically winds his way through a corporate bureaucracy.
In the present invention, a digital signature is certified in a way which indicates the authority the has been granted to the party being certified (the certifiee). The certifier in constructing a certificate generates a special message that includes fields identifying the public key which is being certified, and the name of the certifiee. In addition, the certificate constructed by the certifier includes the authority which is being granted and limitations and safeguards which are imposed including information which reflects issues of concern to the certifier such as, for example, the monetary limit for the certifiee and the level of trust which is granted to, the certifiee. The certificate may also specify co-signature requirements as being imposed upon the certifiee
The present invention further provides for certifying digital signatures such that requirement for further joint certifying signatures is made apparent to any receiver of a digital message. The requirement for joint signatures is especially useful in transactions where money is to be transferred or authorized to be released. To accomplish this end, the certificate of the present invention is constructed to reflect (in addition to the public key and the name of the certifiee and other fields) the number of joint signatures required and an indication as to the identity of qualifying joint signers. Thus, an explicit list of each of the other public key holders that are required to sign jointly may be included in the certificate. In this fashion, the recipient is informed that any material which is signed by the authority of the sender's certificate, must also be signed by a number of other specified signators. The recipient is therefore able to verify other joint and counter signatures by simply comparing the public keys present in each signature in the certificate. The present invention also includes other ways of indicating co-signature requirements such as by indicating other certificates. Such indications of other public key holders may be explicit (with a list as described here), or implicitly, by specifying some other attribute or affiliation. This attribute or affiliation may also be indicated in each co-signer' certificate.
Additionally, the present invention provides for the certification of digital signatures such that a trust level is granted to the recipient for doing subcertifications. In this manner, a trust level of responsibility flows from a central trusted source.
In an exemplary embodiment of the present invention, a certifier is permitted to assign with one predetermined digital code a trust level which indicates that the certifier warrants that the user named in the certificate is known to the certifier and is certified to use the associated public key. However, by virtue of this digital code, the user is not authorized to make any further identifications or certifications on the certifier's behalf. Alternatively, the certifier may issue a certificate having other digital codes including a code which indicates that the user of the public key is trusted to accurately identify other persons on the certifier's behalf and is further trusted to delegate this authority as the user sees fit.
The present invention further provides for a user's public key to be certified in multiple ways (e.g., certificates by different certifiers). The present invention contemplates including the appropriate certificates as part of a user's signed message. Such certificates include a certificate for the signer's certifier and for the certifiers' certifier, etc., up to a predetermined certificate which is trusted by all parties involved. When this is done, each signed message unequivocally contains the ladder or hierarchy of certificates and the signatures indicating the sender's authority. A recipient of such a signed message can verify that authority such that business transactions can be immediately made based upon an analysis of the signed message together with the full hierarchy of certificates.